package LeetCode;

public class LC_137_SingleNumberII {
    public static void main(String[] args) {

    }

    static class Solution {
        public int singleNumber(int[] nums) {
            int[] count = new int[32];
            int result = 0;
            for (int i = 0; i < 32; i++) {
                for (int n : nums) {
                    // 统计第i位的1的个数
                    if (((n >> i) & 1) == 1) count[i]++;
                }
                result |= (count[i] % 3) << i;
            }
            return result;
        }

        public int singleNumber2(int[] nums) {
            // 只出现一次的掩码变量，
            int ones = 0;
            // 只出现两次次的掩码变量
            int twos = 0;
            // 只出现三次的掩码变量
            int threes;

            for (int n : nums) {
                twos |= ones & n;
                // 异或3次 和 异或 1次的结果是一样的
                ones ^= n;
                // 对于ones和twos把出现了3次的位置设置为0（取反之后1的位置为0）
                threes = ones & twos;
                ones &= ~threes;
                twos &= ~threes;
            }

            return ones;
        }
    }
}
